﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 独立钻石
{
    class Program
    {
        /// <summary>
        /// 求解时间约7分钟
        /// 配置：编译器vs2019，电脑内存>=16G
        /// </summary>
        static void Main()
        {
            /// 广度优先
            /// 注意去重
            /// 去除同型
            /// 递归结果

            //开始时刻
            DateTime start = DateTime.Now;
            //队列达到的最大长度
            int count = 0;
            Console.WriteLine("求解开始");

            Aspect aspect = new();

            Queue<Aspect> queue = new();
            queue.Enqueue(aspect);
            HashSet<string> set = new();
            while (queue.Any())
            {
                Aspect now = queue.Dequeue();
                List<Tuple<int, int, Turn>> steps = now.Steps();
                foreach (var step in steps)
                {
                    Aspect next = new(now, step);

                    string self = ToString(next.map);
                    if (!set.Contains(self))
                    {
                        List<string> mays = 各种变换(next.map);
                        foreach (string may in mays)
                        {
                            try
                            {
                                set.Add(may);
                            }
                            catch { }
                        }

                        queue.Enqueue(next);
                        count = Math.Max(queue.Count, count);
                        if (next.success)
                        {
                            Print(next);
                            break;
                        }
                    }
                }
            }

            Console.WriteLine("求解结束");
            //结束时刻
            DateTime end = DateTime.Now;
            Console.WriteLine($"耗时:{(end - start).TotalSeconds}秒");
            Console.WriteLine($"解空间:{count}");
        }

        /// <summary>
        /// 递归打印结果
        /// </summary>
        /// <param name="aspect"></param>
        public static void Print(Aspect aspect)
        {
            if (aspect.parent != null)
            {
                Print(aspect.parent);
            }

            if (aspect.step != null)
            {
                Console.WriteLine($"第{aspect.th}步=={aspect.step.Item1},{aspect.step.Item2},{aspect.step.Item3}");
            }
        }

        /// <summary>
        /// 棋局字符串化，保证唯一
        /// </summary>
        /// <param name="map"></param>
        /// <returns></returns>
        public static string ToString(bool[,] map)
        {
            StringBuilder sb = new();
            for (int i = 1; i <= 7; i++)
            {
                int line = 0;
                for (int j = 1; j <= 7; j++)
                {
                    if (map[i, j])
                    {
                        line |= (1 << (j - 1));
                    }
                }
                sb.Append((char)line);
            }
            return sb.ToString();
        }

        /// <summary>
        /// 正方形的8种“同型”局面字符串
        /// </summary>
        /// <param name="map"></param>
        /// <returns></returns>
        public static List<string> 各种变换(bool[,] map)
        {
            List<string> result = new();
            //本身
            //垂直轴对称
            //水平轴对称
            //撇轴对称
            //捺轴对称
            //顺时针90度
            //逆时针90度
            //中心对称

            StringBuilder[] sbs = new StringBuilder[8];
            for(int i = 0; i < sbs.Length; i++)
            {
                sbs[i] = new();
            }
            int[] line = new int[8];

            for (int i = 1; i <= 7; i++)
            {
                for(int j = 0; j < 8; j++)
                {
                    line[j] = 0;
                }
                for (int j = 1; j <= 7; j++)
                {
                    if(map[i, 8 - j])
                    {
                        line[0] |= (1 << (j - 1));
                    }
                    if(map[8 - i, j])
                    {
                        line[1] |= (1 << (j - 1));
                    }
                    if(map[j, i])
                    {
                        line[2] |= (1 << (j - 1));
                    }
                    if(map[8 - j, 8 - i])
                    {
                        line[3] |= (1 << (j - 1));
                    }
                    if(map[8 - i, 8 - j])
                    {
                        line[4] |= (1 << (j - 1));
                    }
                    if (map[j, 8 - i])
                    {
                        line[5] |= (1 << (j - 1));
                    }
                    if(map[8 - j, i])
                    {
                        line[6] |= (1 << (j - 1));
                    }
                    if (map[i, j])
                    {
                        line[7] |= (1 << (j - 1));
                    }
                }

                for(int j = 0; j < 8; j++)
                {
                    sbs[j].Append((char)line[j]);
                }
            }

            for(int i = 0; i < 8; i++)
            {
                result.Add(sbs[i].ToString());
            }

            return result;
        }
    }
}
